#ifndef BM_CAL_HPP
#define BM_CAL_HPP

#include <vector>
#include <list>
#include <string>
#include <algorithm>



template <class CharType>
class CBMOpers
{
public:
    #define LEN 256
    typedef unsigned int uint;
    typedef struct resultele_t
    {
        uint m_tag;
        uint m_start;
        uint m_end;
        
        struct resultele_t():
        m_tag(0),m_start(0), m_end(0)
        {
        }

        friend std::ostream& operator << (std::ostream& outter, const struct resultele_t& data)
        {
            outter << data.m_tag<< std::endl;
            return outter;
        }

    }resultele;

private:
    int last(std::vector<CharType>& p, CharType c)
    {
        int length = (int)(p.size());
        int count = 0;
        std::vector<CharType>::iterator aiter = p.end();
        if(aiter > p.begin())
        {
            --aiter;
        }
        else
        {
            return -1;
        }
        while(aiter >= p.begin())
        {
            if(*aiter == c)
            {
                return length - count - 1;
            }

            if(aiter == p.begin())
            {
                break;
            }
            --aiter;
            ++count;
        }
        return -1;
    }

public:    
    void query_f(std::vector<CharType>& s, std::vector<CharType>& p, uint tag)
    {
         int n = (int)(s.size());
         int m = (int)(p.size());
         int i=m-1; 
         int j=m-1;
         while(i <= n-1)
         {
             if(s[i] == p[j])
             {
                 if(j == 0)
                 {
                     resultele ares;
                     ares.m_tag = tag;
                     m_results.push_back(ares);
                     return ;
                 }
                 else
                 {
                     i--;
                     j--;
                 }
             }
             else
             {
                 i = i +m - __min(j, 1 + last(p, s[i]));
                 j = m - 1;
             }
         }
         return;
    }
    
    static void stringtovect(const std::string& strdata,  std::vector<CharType>& strvect)
    {        
        uint k = strdata.length();
        strvect.resize(strdata.size());
        std::copy(strdata.begin(), strdata.end(), strvect.begin());        
    }

    void printResult()
    {
        std::list<resultele>::iterator aiter;
        for(aiter = m_results.begin(); aiter != m_results.end(); ++aiter)
        {
            std::cout << *aiter << std::endl;
        }
        std::cout << "_____________________________________________________________"<< std::endl;
    }

private:
    std::vector<uint> m_position;  
    std::list<resultele> m_results;
};
#endif
